package 集合.hashCode与equals;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.function.Supplier;
import java.util.stream.Collectors;
import java.util.stream.Stream;
//linux.words有47万个单词，按不同乘数取哈希值，观察重复与总数的比值(冲突率)
public class hashCodeConflict {
	static int number=235886;//读取的单词总数
	public static void main(String[] args) throws IOException {
		System.out.println("单词总数: "+number);
		List<Integer> multi=List.of(2,3,5,7,17,31,32,36,37,41,47,101,199,201,211,213);//按不同乘数求哈希值
		//Supplier<Stream<String>> streamSupplier = () -> Stream.of(array);
		try (Stream<String> lines = Files.lines(Paths.get("src\\main\\java\\集合\\hashCode与equals\\linux.words")).limit(number)) {
			List<String> list=lines.toList();//之所以要转成List，因为Stream使用后会自动关闭
			for (int i:multi) {
				List<Integer> shashs=list.stream().map((str)->hashCode(str,i)).toList();
				calculateConflictRate(i, shashs);
			};
			//list.forEach(System.out::println);
		} 
      
//		String[] words = new String[]{"Hello","World"};
//      List<String[]> a = Arrays.stream(words)
//              .map(word -> word.split(""))
//              .distinct()
//              .toList();
//      a.forEach(System.out::print);
/*      
      String[] words = new String[]{"Hello","World"};
      List<String> a = Arrays.stream(words)
              .map(word -> word.split(""))
              .flatMap(Arrays::stream)
              .distinct()
              .collect(Collectors.toList()); 
              //.toList();
      a.forEach(System.out::print);
*/
//		try (Stream<String> lines = Files.lines(Paths.get("src\\main\\java\\集合\\hashCode与equals\\linux.words"))) {
//			Supplier<Stream<String>> streamSupplier=()->lines.limit(number);
//			for (int i:multi) {
//				Stream<Integer> hashs=streamSupplier.get().map((str)->hashCode(str,i));
//				List<Integer> lhashs=hashs.toList();
//				calculateConflictRate(i, lhashs);
//			}
//		}

	}
		
	public static Integer hashCode(String str, Integer multiplier) {
	    int hash = 0;
	    for (int i = 0; i < str.length(); i++) {
	        hash = multiplier * hash + str.charAt(i);
	    }
	    return hash;
	}
	    
	/**
	 * 计算 hash code 冲突率，顺便分析一下 hash code 最大值和最小值，并输出
	 * @param multiplier
	 * @param hashs
	 */
	public static void calculateConflictRate(Integer multiplier, List<Integer> hashs) {
//	public static void calculateConflictRate(Integer multiplier, Stream<Integer> hashs) {
	    Comparator<Integer> cp = (x, y) -> x > y ? 1 : (x < y ? -1 : 0);
	    int maxHash = hashs.stream().max(cp).get();
//	    int maxHash = hashs.max(cp).get();
	    int minHash = hashs.stream().min(cp).get();
//	    int minHash = hashs.min(cp).get();

	    // 计算冲突数及冲突率
	    int uniqueHashNum = (int) hashs.stream().distinct().count();
//	    int uniqueHashNum = (int) hashs.distinct().count();
	    int conflictNum = hashs.size() - uniqueHashNum;
//	    int conflictNum = number - uniqueHashNum;
	    double conflictRate = (conflictNum * 1.0) / hashs.size();
//	    double conflictRate = (conflictNum * 1.0) / number;

	    System.out.println(String.format("multiplier=%4d, minHash=%11d, maxHash=%10d, conflictNum=%6d, conflictRate=%.4f%%",
	                multiplier, minHash, maxHash, conflictNum, conflictRate * 100));
	}
}
/*
单词总数: 200000
multiplier=   2, minHash= -865471787, maxHash=2028458647, conflictNum=122764, conflictRate=61.3820%
multiplier=   3, minHash=-2147127927, maxHash=2147481380, conflictNum= 55908, conflictRate=27.9540%
multiplier=   5, minHash=-2147406437, maxHash=2147401178, conflictNum= 18281, conflictRate=9.1405%
multiplier=   7, minHash=-2147414407, maxHash=2147439748, conflictNum=  8942, conflictRate=4.4710%
multiplier=  17, minHash=-2147371371, maxHash=2147476631, conflictNum=  1482, conflictRate=0.7410%
multiplier=  31, minHash=-2147409239, maxHash=2147470403, conflictNum=   264, conflictRate=0.1320%
multiplier=  32, minHash=-2069735039, maxHash=2074694899, conflictNum= 78449, conflictRate=39.2245%
multiplier=  36, minHash=-2147477905, maxHash=2147456371, conflictNum=   444, conflictRate=0.2220%
multiplier=  37, minHash=-2147474523, maxHash=2147434475, conflictNum=   171, conflictRate=0.0855%
multiplier=  41, minHash=-2147470767, maxHash=2147480554, conflictNum=   102, conflictRate=0.0510%
multiplier=  47, minHash=-2147368535, maxHash=2147327558, conflictNum=    64, conflictRate=0.0320%
multiplier= 101, minHash=-2147432552, maxHash=2147467456, conflictNum=     6, conflictRate=0.0030%
multiplier= 199, minHash=-2147480885, maxHash=2147482765, conflictNum=     6, conflictRate=0.0030%
multiplier= 201, minHash=-2147461608, maxHash=2147433287, conflictNum=     5, conflictRate=0.0025%
multiplier= 211, minHash=-2147404700, maxHash=2147452431, conflictNum=     4, conflictRate=0.0020%
multiplier= 213, minHash=-2147474880, maxHash=2147439209, conflictNum=     3, conflictRate=0.0015%

可以看出，使用较小的质数做为乘子时，冲突率会很高。尤其是质数2，冲突率达到了61.3820%。同时我们注意观察质数2作为乘子时，哈希值的分布情况。可以看得出来，
哈希值分布并不是很广，仅仅分布在了整个哈希空间的正半轴部分，即 0 ~ 231-1。而负半轴 -231 ~ -1，则无分布。这也证明了我们上面断言，即质数2作为乘子
时，对于短字符串，生成的哈希值分布性不佳。然后再来看看我们之前所说的 31、37、41 这三个不大不小的质数，表现都不错，冲突数都低于7个。而质
数 101 和 199 表现的也很不错，冲突率很低，这也说明哈希值溢出并不一定会导致冲突率上升。但是这两个家伙一言不合就溢出，我们认为他们不是哈希算法的优选
乘子。最后我们再来看看 32 和 36 这两个偶数的表现，结果并不好，尤其是 32，冲突率超过了了50%。尽管 36 表现的要好一点，不过和 31，37相比，冲突
率还是比较高的。当然并非所有的偶数作为乘子时，冲突率都会比较高。
*/